// https://www.lintcode.com/problem/131/

// 将每个矩形的左边和右边建立两个事件，记下对应高度
// • 对所有事件按X坐标排序
// • 建立高度的最大堆
// • 扫描线
// – 遇到左边事件，堆中加入高度
// – 遇到右边事件，堆中删除高度
// • 堆中最大值即为组合图形现在的高度
// • 将同一个X坐标的事件全部处理完后，如果新高度≠原来的高度，说明出现拐点，记录下来

class Event {
public:
    int x;
    int h;
    int type;
    Event(int x, int h, int type) {
        this->x = x;
        this->h = h;
        this->type = type;
    }
    bool operator < (const Event& e) const {
        // return this->x < e.x || (this->x == e.x && this->h * this->type < e.h * e.type);
        return this->x < e.x || (this->x == e.x && this->h * this->type > e.h * e.type);
    }
};
class Solution {
public:
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    vector<vector<int>> buildingOutline(vector<vector<int>> &buildings) {
        vector<Event> events;
        for (auto building: buildings) {
            events.push_back(Event(building[0], building[2], 1));
            events.push_back(Event(building[1], building[2], -1));
        }
        sort(events.begin(), events.end());
        multiset<int> height;
        vector<vector<int>> rec;
        for (const auto& e: events) {
            int max_height = 0;
            if (!height.empty()) {
                max_height = *height.rbegin();
            }
            if (e.type == 1) {
                height.insert(e.h);
                if (*height.rbegin() != max_height) {
                    rec.push_back({e.x, e.h});
                }
            } else {
                height.erase(height.lower_bound(e.h));
                int new_max_height = 0;
                if (!height.empty()) {
                    new_max_height = *height.rbegin();
                }
                if (new_max_height != max_height) {
                    rec.push_back({e.x, new_max_height});
                }
            }
        }
        vector<vector<int>> ans;
        for (int i = 1; i < rec.size(); ++i) {
            if (rec[i - 1][1] != 0) {
                ans.push_back({rec[i - 1][0], rec[i][0], rec[i - 1][1]});
            }
        }
        return ans;
    }
};